Collection of Tools & Utilities/Collection of Tools and Utilities.iso/basic/ubmalm.zip/malm.doc

Text File | 1989-04-25 | 20KB | 428 lines

14 March 1991

Procedures  ( File : ProcedureList )
All procedures/functions written by Donald E. G. Malm and copyright by him.

For each procedure/function we normally give its Pascal heading, together with
other pertinent information.  The UBASIC versions are like the Pascal versions,
using the same variable names.  The procedures are listed alphabetically,
with the separation of the Pascal routines into the three files BODY 1,2, and 3
indicated.  (The UBASIC subroutines are in individual files.)  There are minor
differences between the UBASIC and Pascal versions, chiefly because UBASIC has
no Boolean or character variables.



**************************    BODY1   *************************************

PROCEDURE BWppt1(n : number; VAR f : integer);
{ Baillie-Wagstaff Lucas pseudoprime test.  See their paper.  We assume
  n is odd and > 11.  D is chosen by method "A".  f is 1 to indicate that n
  is a probable prime, 0 for composite, and -1 if n is a square.  Requires
  unit MultiP.  Calls Add, Sub, Mul, Dvd, Dvdby2, Equal, Isqrt, Jacobi, and
  Modd. }
{ 6 June 1990 }
The article is "LUCAS PSEUDOPRIMES", Robert Baillie and Samuel S. Wagstaff, Jr.,
Math. Comp., v. 35 (1980) pp. 1391-1417.


PROCEDURE BWppt2(n : number; VAR f : integer);
{ Baillie-Wagstaff strong Lucas pseudoprime test.  See their paper.  We assume
  n is odd and > 11.  D is chosen by method "A*".  f is 1 to indicate that n
  is a probable prime, 0 for composite and -1 if n is a square.  Requires unit
  MultiP.  Calls Add, Sub, Mul, Dvd, Dvdby2, Isqrt, Equal, Modd, Jacobi, and
  Spwr. }
{ 6 June 1990  }



UBASIC: There is a subroutine Cgcd(A,B,&C,&Ca,&Cb). This is part of the unit
MultiP in the Pascal versions.



PROCEDURE Chinese(n:longint; VAR A,B,M:Chn; VAR soln, modulus : number);
{ Algorithm for Chinese remaindering of the system A[i] X = B[i] (mod M[i]),
  1 = 1,..,n.  It is NOT assumed that the moduli M[i] are pairwise relatively
  prime.  Soln holds the solution. If there is no solution, modulus = 0,
  otherwise modulus is the modulus of uniqueness of the solution.  Variables A,
  B, and M are input variables; they are VAR only for efficiency.  The type Chn
  is imported from the unit MultiP.  Requires MultiP.  Calls Fcgcd, Dvd, Mul,
  Sub, Add, and Mod. Uses the type Chn.  }
{ 4 August. 1990 }



PROCEDURE Confrat(VAR C : tenr; leng : longint; VAR a,b : number);
{ From the finite continued fraction C this procedure calculates the
  rational a/b that corresponds.  Reverses the procedure Ratconf.  Parameter
  C is VAR only for efficiency; it is an input parameter.  leng is the last
  index used in C.  Note that it is assumed that leng >= 0.  Requires unit
  MultiP, including type tenr.  Calls Mul and Add. }
{ 7 Jan. 1990 }


PROCEDURE Elcfctr(n,c1,c2,a : number; VAR f : number);
{ Elliptic curve method to factorize n, returning a factor in f.  The
  parameters c1,c2, and a are chosen randomly - more than one choice
  may be necessary.  Requires unit MultiP.  Calls Add, Sub, Mul, Modd,
  and Gcd.  }
{ 14 March 1991 }


PROCEDURE Fermat(a : number; ubnd : longint; VAR f,g : number);
{  Fermat's method of factoring a.  ubnd limits the number of iterations.
   The factors (or -1 if ubnd is reached) are placed in f and g.  a must
   be positive and odd.  Requires Unit MultiP.  Calls Isqrt, Mul, Add, Sub,
   Equal, and Dvdby2. }
{  30 Dec. 1989 }



UBASIC: There is a subroutine Fcgcd(A,B,&C,&Ca).  This is part of the unit
MultiP in the Pascal versions.



PROCEDURE Gpcftoq(VAR CF : tenr; leng1,leng2 : longint; VAR A,B,C : number);
{ General periodic continued fraction to quadratic routine.  CF contains the
  continued fraction - indexes 0 through leng1 contain the first part before
  the period while indexes leng1+1 through leng2 contain the complete period.
  It is assumed that the continued fraction represents a positive number.
  CF is an input variable, made VAR for efficiency. A, B, and C return the
  coefficients of the quadratic satisfied by the continued fraction z :
  A z^2 + Bz + C = 0.  There is no error checking to detect improper input.
  Requires unit MultiP, including type tenr.  Calls Mul, Add, Sub, Gcd, and Dvd. }
{ 8 Jan. 1990 }


PROCEDURE Lambda(VAR P, M : triala; k : longint; VAR Lam : number);
{ Returns in Lam the value of Carmichael's function - the minimum universal
  exponent.  P, M, and k have the same meaning as in Sigma, and P and M are
  input varaibles - VAR only for efficiency.  Defines by  convention
  Lambda(1) = 0.  Requires unit MultiP, including type triala.  Calls Mul, Sub,
  Dvd, and Gcd.  }
{ 2 May 1990 }


PROCEDURE LDiosys(r,c : integer; VAR A,V : NumMat; VAR soln : Boolean;
                    VAR rank : integer);
{ Solves the linear Diophantine system represented by the (augmented)
  matrix A.  Matrix V contains a record of the manipulations.  A is r by c+1,
  while V is c by c.  Soln is TRUE if there is a solution, otherwise FALSE.
  Rank is the rank of the system.  Contains the function Pivotind.  Requires
  unit MultiP.  Calls Sub, Mul, Dvd, Less, and Modd. Type NumMat is supplied
  by MultiP. }
{ 16 June 1990 }
This is the algorithm described in "A COMPUTER LABORATORY MANUAL FOR NUMBER
THEORY, by Donald E. G. Malm, COMPRess, 1980.


PROCEDURE Lehmer(p,q : number; VAR r : number);
{ D. H. Lehmer's method of solving x^2 = q (mod p), assuming that p is an
  odd prime and q is a quadratic residue modulo p.  The solution is
  returned in r.  Requires unit MultiP.  Calls Add, Sub, Mul, Dvd, Dvdby2,
  Spwr, Equal, Less, Jacobi, and Modd. }
{ 7 June 1990 }
The algorithm is described in Lehmer's article "COMPUTER TECHNOLOGY APPLIED
TO THE THEORY OF NUMBERS", in "STUDIES IN NUMBER THEORY", MAA 1969,
pp. 117 - 151.


FUNCTION Mobius(VAR M : triala; k : longint) : longint;
{ Returns the Mobius function.  M and k have the same meaning as in Tau.
  Requires unit MultiP for the type triala.  Calls no procedures nor functions.}
{ 22 April 1990 }
UBASIC supplies this as a function in the language.



********************************   BODY2   ************************************


PROCEDURE Mppt(n,Q : number; VAR f : Boolean);
{ Implements Malm's probabilistic test for primality (or compositeness).
  Assumes n is odd, not a square, and that (Q|n)=1.  Returns f = TRUE
  if n is probably prime, and f = FALSE if n is composite. Requires unit
  MultiP.  Calls Add,Sub, Mul, Dvdby2, Modd, Gcd, Less, Jacobi, and Equal. }
{ 7 June 1990 }

This procedure Mppt and the following one Mst are very effective unpublished
probable prime tests devised by the author.

PROCEDURE Mst(n : number; VAR f : Boolean);
{ Test for probable primality or compositeness devised by Malm.  Returns
  f = TRUE if n is a probable prime, and f = FALSE if n is composite.  Requires
  unit MultiP.  Calls Add, Sub, Mul, Dvdby2, Modd, Isqrt, Gcd, Equal, Jacobi,and
  Less.  Contains a subprocedure Lehmerc, which is the procedure Lehmer adapted
  to input that is not necessarily prime. }
{ 21 August 1990 }


FUNCTION NxtPrm(a: integer): longint;
 {  Returns the smallest prime greater than a, or else 0 if a < 0 or
    a >= 10,000.  Returns an integer, not a number.  Requires unit MultiP
    for the array prm[]. Calls no procedures nor functions. }
 { 20 April 1990 }
 UBASIC supplies this as a part of the language.


PROCEDURE Pell(d : number; VAR x,y : number; VAR f : longint);
{ Uses continued fractions to compute the smallest nontrivial positive
  solution to x^2 - d y^2 = f, where f is 1 or -1.  Note that f is computed
  by the program; it is not your choice.  f = 0 indicates improper input.
  Requires unit MultiP.  Calls Isqrt, Mul, Sub, Add, Dvd, and Equal. }
{  10 January 1990 }


Procedure Peralta(p,x : number; VAR s : number);
{ Implements Peralta's (second) probabilistic algorithm to compute
  s for which s^2 = x (mod p), assuming that p is an odd prime and that x
  is a quadratic residue modulo p.  Requires unit MultiP.  Calls Add, Sub,
  Mu